package Offer.offer;

import domain.TreeNode;

import java.util.ArrayList;

/**
 * 二叉树中和为某一值的所有路径
 *
 * @author leiwenkang
 * @date 2020/4/6
 */
public class Test25二叉树中和为某一值的所有路径 {
    public static void main(String[] args) {
        TreeNode node1=new TreeNode(10);
        TreeNode node2=new TreeNode(5);
        TreeNode node3=new TreeNode(12);
        TreeNode node4=new TreeNode(4);
        TreeNode node5=new TreeNode(7);
        node1.left=node2;
        node1.right=node3;
        node2.left=node4;
        node2.right=node5;
        node3.left=node3.right=null;
        node4.left=node4.right=null;
        node5.left=node5.right=null;
        findPath(node1,22);
    }
    
    public static void findPath(TreeNode root, int target) {
        if (root == null) {
            return;
        }

        ArrayList<Integer> list = new ArrayList<>();
        findPath(root, target, list, 0);
    }

    private static void findPath(TreeNode root, int target, ArrayList<Integer> list, int sum) {
        list.add(root.val);
        sum += root.val;
        boolean isLeaf = root.left == null && root.right == null;
        if (isLeaf && sum == target) {
            System.out.print("找到路径:");
            for (int i = 0; i < list.size(); i++) {
                System.out.print(list.get(i));
                System.out.print(" ");
            }
            System.out.println();
        }
        if (root.left != null) {
            findPath(root.left, target, list, sum);
        }

        if (root.right != null) {
            findPath(root.right, target, list, sum);
        }
        list.remove(list.size() - 1);
        sum -= root.val;
    }


}
